This application is the U.S. national phase of International Application No. PCT/GB2014/000118 filed 27 Mar. 2014 which designated the U.S. and claims priority to EP Patent Application No. 13250050.5 filed 28 Mar. 2013, the entire contents of each of which are hereby incorporated by reference.
The present invention relates to the field of multicast routing and, in particular embodiments, to systems and method for growing a multicast tree.
In many networks, several end user terminals, or hosts, wish to receive the same data at the same time. This data can include anything from video or audio content to software updates to information about the network itself. While it would be possible to send this information simultaneously and individually to each host in the network, this would involve the transmission of large amounts of replicated data throughout the network. An alternative approach would be to broadcast the data by flooding the whole network with the data and enabling any host that was interesting in receiving the data to do so, while other hosts simply ignore the irrelevant packets. However, there may be significant branches of the network that do not include any hosts that are interested in receiving the data. Therefore, broadcasting methods also risk generating significant amounts of unwanted data in the network.
Methods of multicasting data have therefore been developed in which data is transmitted through the network only to those destinations or hosts that have indicated a desire to receive the data, by joining the multicast group for that data. However, multicast data is replicated in the network only where the route to two destination hosts splits. Therefore, only one copy of the data is sent through the network until routes to the destination hosts diverge. Data is therefore sent out through the network in a multicast tree, from which branches are formed as routes to various destinations diverge.
Multicast routing protocols govern how such multicast trees are formed, as described in more detail below, but usually a request is sent upstream from the host towards the multicast source and the host forms a new branch from the tree at the first upstream router it finds that is already part of the multicast tree.
Khuller et al, “Balancing Minimum Spanning and shortest path trees”, XP055078016 is a theoretical paper that shows that for each graph, (or network) with weighted edges (link costs) a tree exists that connects a number of leaf nodes to a root node and that balances between a minimum spanning tree (i.e. the sum of link costs) and a shortest path tree (where each path from the root to a leaf is the shortest possible path). The paper presents an algorithm to find such a tree and shows that it is optimal. The algorithm finds one tree and that tree does not change or evolve over time.
Ben-Shimol et al, “SPLAST: a novel approach for multicasting in mobile wireless ad hoc networks”, PIMRC 2004, 15th IEEE International Symposium, Barcelona, vol. 2, September 2004, pp 1011-1015, provides an algorithm to build a multicast tree in mobile ad hoc networks. The tree minimises the sum of link costs and the length of the paths from the root. The algorithm also shows how to recover from failing links, change in link cost, and the disappearance and reappearance of edge nodes. The cost of a link between two nodes is defined as a function of the power transmission level that is required to establish a connection between the two nodes. The tree only change if links or nodes change, but it does not evolve with usage for multicasting.
According to one aspect, there is provided a method of managing routing paths in a content delivery network, the method comprising:                determining, according to a unicast routing protocol, a first link cost for a first routing path;        determining a second link cost for a second routing path, the second routing path comprising a first component comprising a link cost to a router that is part of a multicast group and a second component comprising a link cost for the multicast tree from the router;        determining an adjustment factor based on information received from the content delivery network;        applying the adjustment factor to the second link cost;        analysing the adjusted second link cost and the first link cost to determine an adjusted least cost path in the content delivery network; and        selectively outputting the adjusted second link cost to a routing database to influence routing in the content delivery network.        
The method may enable the system to select a routing path that is different from the multicast routing path that would be built using standard unicast routing protocols. The decision to use the alternative routing path can be based on information obtained from the network, as described in more detail below. The second routing path includes a first section that connects the requesting destination to a router that is already part of the multicast group, but that is not part of the standard unicast-created path back towards the source. The second routing path also includes a second section that comprises an existing multicast routing path from the router back to the source, Rendezvous Point (RP) or Source Designated Router (S-DR) for the multicast stream.
The first and/or second routing paths may be multicast routing paths.
In some embodiments, adjustment factors are applied on a per-link basis and the adjusted link cost for the whole route is determined by combining the adjusted per-link values. In other embodiments, the link cost for the route as a whole is determined and an adjustment factor is determined and applied to the link cost for the whole route.
In a particular embodiment, the adjustment factor is calculated based on a predictive model.
The analysing step can determine whether the first or second multicast routing path provides the preferred path along which the stream can be delivered based on the adjusted link cost values. Optionally the path with the lower associated link cost value is the preferred path. If the first path is determined to be the preferred path, then the network is permitted to set up the multicast tree according to the shorted path back to the source. If the second path is determined to be the preferred path, then the adjusted link cost is output to the routing database, which causes the router to set up the multicast path and route the multicast stream along the second path.
In a particular embodiment, the first component of the second link cost comprises a link cost for a unicast path to a router through which passes a branch of the multicast tree. Optionally, the router is not one that is on the path that would be created using unicast routing protocols directly back towards the source, RP or S-DR.
In a particular embodiment, the first component comprises the unicast link cost of the path to the closest router in the multicast tree. Optionally, the closest router can be connected directly to the host designated router (H-DR). Optionally, the closest router comprises a H-DR for at least one other host.
In some embodiments, the second component comprises a link cost for the multicast tree from the branch to a rendezvous point, source designated router or source. Hence, the link cost can be calculated based on the link cost to join the nearest existing branch of a multicast tree and the link cost of the tree from that point back to an RP, S-DR or source for the multicast stream.
In a particular embodiment, the first multicast routing path comprises the shortest path to the RP, S-DR or source as determined according to a unicast routing protocol. This is the path along which the multicast tree would be built if the present multicast management method was not implemented.
In some embodiments, the method further comprises selecting a path for a multicast routing stream based on the adjusted least cost path and routing a multicast routing stream along the selected path.
In a particular embodiment, the method further comprises determining an adjustment factor for the first link cost based on information received from the content delivery network; and applying the adjustment factor to the first link cost. Hence the first link cost may also be an adjusted value based on factors such as those described below.
This may enable a more accurate comparison of the link costs along the first and second paths.
In some embodiments, the information received from the content delivery network comprises availability and/or capacity information for the second multicast routing path.
Optionally, the information received from the content delivery network comprises availability and/or capacity information for the first multicast routing path.
In a particular embodiment, the information received from the content delivery network comprises predicted availability and/or capacity information for one or both of the first and second multicast routing paths. That is, the information may include an indication of the expected capacity or availability of the paths, optionally based on a model of the expected network usage.
Optionally, the information received from the content delivery network comprises at least one of: congestion information; availability information; Quality of Service information; congestion prediction information; availability prediction information; traffic performance data; and traffic performance data prediction.
In one embodiment, the method is implemented in a router in the network. For example, each PIM router in the network may receive the necessary information to manage multicast routing paths according to the methods described herein.
In another embodiment, the method is implemented at a central network component and transmitted to one or more routers. Hence the central network component may calculate adjusted link cost values for paths in the network and push this information to PIM routers in the network.
In one embodiment, outputting the adjusted second link cost to a routing database comprises saving the adjusted second link cost to a Multicast Routing Information Base (MRIB). The adjusted cost optionally replaces and overwrites the first link cost in the MRIB.
In an alternative embodiment, outputting the adjusted second link cost to a routing database comprises transmitting the adjusted second link cost to at least one router in the network. Routers receiving the adjusted link cost can then add this information into their MRIBs.
In a particular embodiment, the method further comprises determining and adjusting a link cost for at least one further multicast routing path and analysing the adjusted link cost for the further multicast routing path to determine the least cost path in the content delivery network. Hence three or more paths may be analysed according to the methods described herein with the best path being selected for the multicast stream. This may be useful, for example, if there are several routers close to the requesting destination that are already members of the multicast tree.
Optionally, the information received from the content delivery network comprises traffic parameters made available on a per link basis. The method may further include collecting the traffic parameters on a per link basis.
In some embodiments, the traffic parameters are measured continually or periodically.
The method may further include collecting traffic parameters for links to neighbouring routers.
Optionally, the traffic information includes at least one of: bandwidth; delay; jitter; and delivery rate.
In some embodiments, the traffic information further comprises the rate of change of explicit congestion notifications (ECN) for the link.
Optionally, the traffic information is input into a training database for use by the predictive model.
In a particular embodiment, the traffic performance for a whole route is determined by combining values determined for individual links. In particular, the overall bandwidth for a route may be determined by the bandwidth of the minimum bandwidth link, the overall delay may be determined by the sum of the delay values per link, the overall jitter may be determined by the sum of the jitter values per link and the overall delivery rate may be determined by the delivery rate of the minimum rate link.
In some embodiments, the predictive model includes a prediction of how long the service level agreement for the multicast session can be guaranteed on the link.
Optionally, the method further comprises setting a flag in the routing table to indicate that the stored link cost is an adjusted link cost.
Optionally, the method further comprises setting at least one bit in a Join/Prune message to indicate that the route has been determined according to the methods described above.
Therefore, in some embodiments, there is provided a method for autonomously growing a multicast tree based on traffic considerations and network performance. When a PIM-SM enabled router receives a Membership Report from one of its IGMP-enabled hosts, it can perform a set of predictive data analytics evaluations to decide the best route to create its tree back to the source or the RP. Embodiments of the system described herein exist as an entity that maps a unicast routing metric to change the multicast routing metric in the MRIB (Multicast Routing Information Base), taking into account a set of multicast tree and unicast-related weighting factors. This change is reflected in its choice of Reverse Path Forwarding (RPF) next-hop neighbour to send group Join/Prune messages and also is used in Assert messages.
Factors that can be taken into account are such that the shape of the tree will slowly evolve in time, depending on current and predicted performance of various branches. It will branch out if the existing RPT is congested or expected to perform badly for the given service, or grow to exploit an existing tree and narrow down, thus preventing data replication in the network when the tree can sustain the data streams' demands. This demonstrates autonomous tree growth, depending on network conditions.
According to a second aspect, there is provided apparatus for managing routing paths in a content delivery network, the apparatus comprising:
means for determining a first link cost for a first routing path according to a unicast routing protocol;
means for determining a second link cost for a second routing path, the second routing path comprising a first component comprising a link cost to a router that is part of the multicast group and a second component comprising a link cost for the multicast tree from the router;
means for determining an adjustment factor for the second link cost based on information received from the content delivery network;
means for applying the adjustment factor to the second link cost;
means for analysing the adjusted second link cost and the first link cost to determine an adjusted least cost path in the content delivery network; and
means for selectively outputting the adjusted second link cost to a routing database to influence routing in the content delivery network.
There is also provided herein apparatus for managing multicast routing paths in a content delivery network, the apparatus comprising a processor arranged for or logic configured for:                determining a first link cost for a first multicast routing path according to a unicast routing protocol;        determining a second link cost for a second multicast routing path, the second multicast routing path comprising a first component comprising a link cost to a router that is part of the multicast group and a second component comprising a link cost for the multicast tree from the router;        determining an adjustment factor for the second link cost based on information received from the content delivery network;        applying the adjustment factor to the second link cost;        means for analysing the adjusted second link cost and the first link cost to determine an adjusted least cost path in the content delivery network; and        selectively outputting the adjusted second link cost to a routing database to influence routing in the content delivery network.        
A further aspect provides a computer program, computer program product or computer readable medium or logic arranged to implement any of the methods described above.
There is also provided a method according to any one described herein with reference to the figures and apparatus according to any described herein with reference to the figures.
A number of embodiments of the system have been described above. It will be clear to one skilled in the art that embodiments may be implemented independently. However, the embodiments are optionally implemented in conjunction with each other to provide multiple advantages as part of a larger system. Features of one aspect may be applied directly to other aspects of the system. Further, method features may be applied directly to aspects of the apparatus.
In particular, in all of the aspects described above, the destination may be a host or a host designated router, H-DR, in a multicast network. The host may be the end user terminal associated with an end user or consumer of the content or may be an intermediate device that serves the content to the user's device. For example, the destination may be a hub within a home network that receives the content for streaming to a user's terminal, such as an internet-connected television, a computer, a tablet or a telephone.
Similarly, in all of the aspects described above, the source may be the device that serves the content in the network or may be an intelligent routing component in the network that handles routing of content to destinations. The content may pass through the intelligent routing component, or the component may control other components in the network, such as the source, to implement the methods described herein.
Further, in all of the aspects set out above, the content is optionally video content and/or audio content, in particular on-demand content delivered in response to a request from a user. However, the skilled person will appreciate that the systems and methods described herein could equally be applied to networks for the distribution of data, such as text or image data, or software.